﻿// Copyright (c) 2010 Dan Popick

// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using Open.Web.Stijl.Utility;

namespace Open.Web.Stijl
{
    public class SpriteCategorizer
    {
        public SpriteCategorizer()
        {
        }

		/// <summary>
		/// Groups sprites into containers of like types
		/// </summary>
		/// <param name="sprites">A set of sprites to group</param>
		/// <returns>A list of containers</returns>
        public List<SpriteContainer> Categorize(IEnumerable<Sprite> sprites)
        {
            List<SpriteContainer> finalGroups = new List<SpriteContainer>();

            // sort into groups; all indexed images go into an 8bpp group.
            var gr = from x in sprites
                     group x by new {
							Repeat = x.Repeat,
							Format = x.Format.IsIndexed() ? System.Drawing.Imaging.PixelFormat.Format8bppIndexed : x.Format
						}
                        into spriteGroup
                     select AggregateSets(CombineSubsets(spriteGroup));

            foreach (var list in gr)
                finalGroups.AddRange(list);

            return finalGroups;
        }

        /// <summary>
        /// Combines all sprites which are sub/supersets of each other
        /// </summary>
        /// <param name="sprites"></param>
        List<SpriteContainer> CombineSubsets(IEnumerable<Sprite> sprites)
        {
            List<SpriteContainer> groups = new List<SpriteContainer>();
            List<Sprite> spriteList = 
                (from x in sprites
                orderby x.Colors.Count
                select x).ToList();

            int end = spriteList.Count - 1;
            while (spriteList.Count > 0)
            {
                Sprite groupIm = spriteList[spriteList.Count - 1];
                SpriteContainer container = new SpriteContainer(groupIm.Format, groupIm.Repeat);

                container.Add(groupIm);

                // remove the item itself
                spriteList.RemoveAt(spriteList.Count - 1);

                // remove all items which it can be combined with
                spriteList.RemoveAll(im => Matches(container, im));

                groups.Add(container);
            }

            return groups;
        }

        bool Matches(SpriteContainer container, Sprite sprite)
        {
            if (sprite.Format != container.Format)
                return false;

            ColorHistogram or = container.ColorHistogram | sprite.ColorHistogram;
            bool subset = or == container.ColorHistogram || or == sprite.ColorHistogram;

            if (subset)
            {
                if (container.Colors.Count > sprite.Colors.Count)
                    subset = container.Colors.IsSupersetOf(sprite.Colors);
                else
                    subset = container.Colors.IsSupersetOf(container.Colors);

                if (subset)
                    container.Add(sprite);
            }

            return subset;
        }

        List<SpriteContainer> AggregateSets(List<SpriteContainer> containers)
        {
            // the results
            List<SpriteContainer> final = new List<SpriteContainer>();

            // sort the containers by color count
            containers.Sort((x, y) => x.Colors.Count - y.Colors.Count);

            while (containers.Count > 0)
            {
                // take the last (largest) container
                SpriteContainer workingContainer = containers[containers.Count - 1];
                containers.RemoveAt(containers.Count - 1);

                // if it's at capacity, move it to the final solution list and
                // continue with the next container
                if (workingContainer.Colors.Count == 256)
                {
                    final.Add(workingContainer);
                    continue;
                }

                // Sort remaining containers by the color difference between them
                // and ig, descending
                var elg = containers.Select(
                    (x, i) => new { 
                        Index = i, // not used, but could be used for logging
                        Diff = workingContainer.Colors.GetOverlap(x.Colors),
                        TotalColors = x.Colors.Count + workingContainer.Colors.Count,
                        Container = x 
                    }).OrderByDescending(x => x.TotalColors - x.Diff);

                // attempt to combine the sets, starting with the largest first
                foreach (var x in elg)
                {
                    // if the resulting difference is too great, skip and continue
                    if (x.Diff + workingContainer.Colors.Count > 256)
                        continue;

                    // otherwise add it to the working container
                    workingContainer.Add(x.Container);
                    containers.Remove(x.Container);
                }

                // at this point the container has picked up all the sprites it can handle,
                // so we add it to the final container list
                final.Add(workingContainer);
            }

            return final;
        }
    }
}
